class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = new Node('head')
  }
  // 根据value查找节点
  findByValue(item) {
    let currentNode = this.head
    while (currentNode !== null && currentNode.element !== item) {
      currentNode = currentNode.next
    }
    return currentNode === null ? -1 : currentNode
  }
  // 根据index查找节点
  findByIndex(index) {
    let currenNode = this.head
    let pos = 0
    while (currenNode !== null && pos !== index) {
      currenNode = currenNode.next
      pos++
    }
    return currenNode === null ? -1 : currenNode
  }
  // 指定元素向后插入
  insert(newElement, element) {
    let currenNode = this.findByValue(element)
    if (currenNode === -1) {
      return
    }
    const newNode = new Node(newElement)
    newNode.next = currenNode.next
    currentNode.next = newNode
  }
  // 查找前一个
  findPrev(item) {
    let currenNode = this.head
    while (currenNode.next !== null && currenNode.next.element !== item) {
      currenNode = currenNode.next
    }
    return currentNode === null ? -1 : currentNode
  }
  // 根据
  remove(item) {
    let currenNode = this.findByValue(item)
    if (currenNode === -1) {
      return
    }
    const preNode = this.findPrev(item)
    preNode.next = currenNode.next
  }
  // 遍历显示所有节点
  display() {
    if (this.hasCycle()) {
      return
    }
    let currenNode = this.head
    while (currenNode !== null) {
      console.log(currenNode.element)
      currenNode = currenNode.next
    }
  }
  // 检查是否有环-哈希表
  hasCycle() {
    const head = this.head
    const seen = new Set()
    while (head != null) {
      if (!seen.has(head)) {
        return true
      }
      seen.add(head)
      head = head.next
    }
    return false
  }
  // 检查是否有环-Floyd 判圈算法
  hasCycle1() {
    let fast = this.head.next
    let slow = this.head
    while (fast !== null && fast.next !== null) {
      fast = fast.next.next
      slow = slow.next
      if (slow === fast) return true
    }
    return false
  }
  // 已知链表中有环，返回这个环的起始位置
  detectCycle() {
    let fast = (slow = this.head)
    while (fast !== null && fast.next !== null) {
      fast = fast.next.next
      slow = slow.next
      if (slow === fast) break
    }

    slow = this.head
    while (slow != fast) {
      fast = fast.next
      slow = slow.next
    }
    return slow
  }
  // 寻找无环链表的中点
  // 利用双指针，快指针一次走两步，慢指针一次走一步，快指针到达终点时，慢指针就处于链表的中间位置
  findMid() {
    let fast = (slow = this.head)
    while (fast != null && fast.next != null) {
      fast = fast.next.next
      slow = slow.next
    }
    return slow
  }
  /**
   * 寻找单链表的倒数第K个元素
   * 思路：使用快慢指针，让快指针先走K步，然后快慢指针开始同速前进。
   * 快指针走到链表末尾时，慢指针所在的位置就是倒数第K个链表节点。
   */
  findK(k) {
    let fast = (slow = this.head)
    while (k != 0) {
      fast = fast.next
      k--
    }
    while (fast != null && fast.next != null) {
      fast = fast.next
      slow = slow.next
    }
    return slow
  }
  // reverse 反转链表
  reverseList() {
    const root = new Node('head')
    let currenNode = this.head.next
    while (currenNode != null) {
      const next = currenNode.next
      currenNode.next = root.next
      root.next = currenNode
      currenNode = next
    }
    this.head = root
  }
}

new LinkedList()
